export interface Hashable {
    hashcode(): string,
    equals(x: this): boolean
}

/**
 * Note: the code for this class is written by GPT-3.5, with minor modifications
 */
export class HashSet<T extends Hashable> {
    private data: Map<string, T[]>;

    constructor(...vals: T[]) {
        this.data = new Map<string, T[]>();
        for (let v of vals)
            this.add(v);
    }

    // Method to add an element to the set
    add(value: T): void {
        const hashcode = value.hashcode();
        if (!this.data.has(hashcode)) {
            // No collision, create a new list for this hashcode
            this.data.set(hashcode, [value]);
        } else {
            // Collision, add to the existing list
            const candidates = this.data.get(hashcode) as T[];
            if (!candidates.some(candidate => value.equals(candidate))) {
                // Add only if the element is not already present
                candidates.push(value);
            }
        }
    }

    // Method to check if an element is present in the set
    has(value: T): boolean {
        const hashcode = value.hashcode();
        if (this.data.has(hashcode)) {
            const candidates = this.data.get(hashcode) as T[];
            return candidates.some(candidate => value.equals(candidate));
        }
        return false;
    }

    // Method to delete an element from the set
    delete(value: T): boolean {
        const hashcode = value.hashcode();
        if (this.data.has(hashcode)) {
            const candidates = this.data.get(hashcode) as T[];
            const index = candidates.findIndex(candidate => value.equals(candidate));

            if (index !== -1) {
                candidates.splice(index, 1);
                if (candidates.length === 0) {
                    // Remove the hashcode entry if no candidates left
                    this.data.delete(hashcode);
                }
                return true;
            }
        }
        return false;
    }

    // Method to get the size of the set
    get size(): number {
        let count = 0;
        this.data.forEach(candidates => count += candidates.length);
        return count;
    }

    // Method to clear all elements from the set
    clear(): void {
        this.data.clear();
    }

    // Method to iterate over elements in the set
    forEach(callback: (value: T, value2: T, set: HashSet<T>) => void): void {
        this.data.forEach((candidates, hashcode) => {
            candidates.forEach(element => {
                callback(element, element, this);
            });
        });
    }

    *[Symbol.iterator]() {
        for (let [_, vs] of this.data)
            for (let v of vs)
                yield v;
    }
}

/**
 * Note: the code for this class is written by GPT-3.5, with minor modifications
 */
export class HashMap<T extends Hashable, V> {
    private data: Map<string, [T, V][]>;

    constructor() {
        this.data = new Map<string, [T, V][]>();
    }

    // Method to put a key-value pair into the map
    set(key: T, value: V): void {
        const hashcode = key.hashcode();
        const candidates = this.data.get(hashcode);
        if (!candidates) {
            // No collision, create a new list for this hashcode
            this.data.set(hashcode, [[key, value]]);
        } else {
            // Collision, add to the existing list
            const existingEntry = candidates.find(entry => key.equals(entry[0]));

            if (existingEntry) {
                // Update the value if the key already exists
                existingEntry[1] = value;
            } else {
                // Add a new entry for the collided key
                candidates.push([key, value]);
            }
        }
    }

    // Method to get the value associated with a key
    get(key: T): V | undefined {
        const hashcode = key.hashcode();
        const candidates = this.data.get(hashcode);
        if (candidates) {
            const entry = candidates.find(entry => key.equals(entry[0]));
            return entry ? entry[1] : undefined;
        }
        return undefined;
    }

    // Method to check if a key is present in the map
    has(key: T): boolean {
        const hashcode = key.hashcode();
        const candidates = this.data.get(hashcode);
        if (candidates) {
            return candidates.some(entry => key.equals(entry[0]));
        }
        return false;
    }

    // Method to delete a key-value pair from the map
    delete(key: T): boolean {
        const hashcode = key.hashcode();
        const candidates = this.data.get(hashcode);
        if (candidates) {
            const index = candidates.findIndex(entry => key.equals(entry[0]));

            if (index !== -1) {
                candidates.splice(index, 1);
                if (candidates.length === 0) {
                    // Remove the hashcode entry if no candidates left
                    this.data.delete(hashcode);
                }
                return true;
            }
        }
        return false;
    }

    // Method to get the size of the map
    get size(): number {
        let count = 0;
        this.data.forEach(candidates => count += candidates.length);
        return count;
    }

    // Method to clear all key-value pairs from the map
    clear(): void {
        this.data.clear();
    }

    // Method to iterate over key-value pairs in the map
    forEach(callback: (value: V, key: T, map: HashMap<T, V>) => void): void {
        this.data.forEach((candidates, hashcode) => {
            candidates.forEach(entry => {
                callback(entry[1], entry[0], this);
            });
        });
    }

    *[Symbol.iterator]() {
        for (let [_, vs] of this.data)
            for (let v of vs)
                yield v;
    }
}